package own.stu.jobgib.playown.alg.solution.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合
 * 回溯
 */
public class Combination {

    public static void main(String[] args) {
        Combination b = new Combination();
        /*System.out.println(b.combinationSum(new int[]{2, 3, 6, 7}, 7));
        System.out.println(b.combinationSum(new int[]{2, 3, 5}, 8));*/

        /*System.out.println(b.combine(4, 2));*/

        /*System.out.println(b.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
        System.out.println(b.combinationSum2(new int[]{2, 5, 2, 1, 2}, 5));*/

        System.out.println(b.combinationSum3(3, 7));
        System.out.println(b.combinationSum3(3, 9));
    }

    /**
     * 39. 组合总和
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
     * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
     * <p>
     * 输入：candidates = [2,3,6,7], target = 7
     * 输出：[[2,2,3],[7]]
     * 解释：
     * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
     * 7 也是一个候选， 7 = 7 。
     * 仅有这两种组合。
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0 || target <= 0) {
            return ans;
        }

        Arrays.sort(candidates);  // 排序的目的是为了后边更好的剪枝
        combinationSumHelper(ans, candidates, target, 0, new ArrayList<>());

        return ans;
    }

    private void combinationSumHelper(List<List<Integer>> ans, int[] candidates, int target, int start, ArrayList<Integer> list) {

        if (target <= 0) { // target 控制递归结束
            if (target == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) { // 剪枝
                break;
            }
            list.add(candidates[i]);
            combinationSumHelper(ans, candidates, target - candidates[i], i, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 40. 组合总和 II
     * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用 一次 。
     * <p>
     * 注意：解集不能包含重复的组合。
     * <p>
     * 示例 1:
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
     * 输出:
     * [[1,1,6],[1,2,5],[1,7],[2,6]]
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || candidates.length == 0 || target <= 0) {
            return ans;
        }

        Arrays.sort(candidates);  // 排序的目的是为了后边更好的剪枝

        combinationSum2Helper(ans, candidates, target, 0, new ArrayList<>());

        return ans;
    }

    private void combinationSum2Helper(List<List<Integer>> ans, int[] candidates, int target, int start, List<Integer> list) {
        if (target <= 0) {
            if (target == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        for (int i = start; i < candidates.length; i++) {

            if (candidates[i] > target) {
                break;
            }

            /*
             * i != start ，start 是上一层递归的下标，
             * [1 ,1, 2] target = 3;  如果start = 0 ，当前 i = 1时，此时的遍历情形在 上一层都已经遍历过了。
             * 这里可以使用 visited[i] 数组 来判断 i != 0 && nums[i] == nums[i - 1] && visited[i - 1] = false 时，才可以继续遍历
             */
            if (i != start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            list.add(candidates[i]);
            combinationSum2Helper(ans, candidates, target - candidates[i], i + 1, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 216. 组合总和 III
     * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
     * <p>
     * 只使用数字1到9
     * 每个数字 最多使用一次
     * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
     * <p>
     * 示例 1:
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * 解释:
     * 1 + 2 + 4 = 7
     * 没有其他符合的组合了。
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        if (k <= 1 || n <= 0) {
            return ans;
        }
        combinationSum3Helper(ans, 1, k, n, new ArrayList<Integer>());

        return ans;
    }

    private void combinationSum3Helper(List<List<Integer>> ans, int start, int left, int target, List<Integer> list) {
        if (target <= 0 || left <= 0) {
            if (target == 0 && left == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        int last = 9 - left + 1;
        for (int i = start; i <= last; i++) {
            if (i > target) {
                break;
            }
            list.add(i);
            combinationSum3Helper(ans, i + 1, left - 1, target - i, list);
            list.remove(list.size() - 1);
        }

    }

    /**
     * 377. 组合总和 Ⅳ
     * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
     * <p>
     * 题目数据保证答案符合 32 位整数范围。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3], target = 4
     * 输出：7
     * 解释：
     * 所有可能的组合为：
     * (1, 1, 1, 1)
     * (1, 1, 2)
     * (1, 2, 1)
     * (1, 3)
     * (2, 1, 1)
     * (2, 2)
     * (3, 1)
     * 请注意，顺序不同的序列被视作不同的组合。
     */
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return 0;
        }

        // TODO 不是 回溯 ...
        return 0;
    }

    /**
     * 77. 组合
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * <p>
     * 你可以按 任何顺序 返回答案。
     * 示例 1：
     * <p>
     * 输入：n = 4, k = 2
     * 输出：
     * [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        if (n <= 0 || k <= 0 || k > n) {
            return ans;
        }

        combineHelper(ans, 1, new ArrayList<>(), k, n);

        return ans;
    }

    private void combineHelper(List<List<Integer>> ans, int start, List<Integer> list, int k, int n) {
        if (k <= 0) { // k 表示遍历的层数，来控制递归的结束
            if (k == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        /*
        k 即表示层数，也表示剩余的数字，如果n = 5, 当前k为3，即还需要取三个数字，此时i最多可以取值到 3 (n - k + 1)，i 如果取4， 就不够k个数字了，只剩余 4，5
        因此这里 可以剪枝
         */
        int last = n - k + 1;
        for (int i = start; i <= last; i++) {
            list.add(i);
            combineHelper(ans, i + 1, list, k - 1, n);
            list.remove(list.size() - 1);
        }
    }

}
